#include <iostream>
#include <vector>

using namespace std;

/**
 * @brief The Solution class 93 复原ip地址
 */
class Solution {
public:
    Solution() : ret(), path(),n(0)
    {

    }
public:
    vector<string> restoreIpAddresses(const string& s) {
        n = s.size();
        if(n < 4 || n > 12)
        {
            return ret;
        }

        dfs(s,0);
        return ret;
    }

private:
    void dfs(const string& s,int i)
    {
        if(path.size() == 4)
        {
            string str;

            for(int k=0; k<4; k++)
            {
                // 剔除：先导不能为0
                string& part = path[k];
                if(part.size() != 1 && part[0] == '0')
                {
                    // 先导为0，剔除
                    str = "";
                    break;
                }

                if(k > 0)
                {
                    str += ".";
                }
                str += part;

            }

            // 剔除：没用全部用尽s中的元素
            if(str.size() - 3 != n)
            {
                str = "";
            }

            if(!str.empty())
            {
                ret.push_back(str);
            }

            return;
        }
        // 0~255 一次取3个数
        for(int j = 1; j <= 3; j++)
        {
            // 不能取超过了s的范围
            if(i + j <= n)
            {
                string str = s.substr(i,j);
                int value = std::stoi(str);
                if(0 <= value && value <= 255)
                {
                    path.push_back(str);
                    dfs(s, i+j);
                    path.pop_back();
                }
            }
        }
    }
private:
    vector<string> ret;
    vector<string> path;
    int n;

};


//int main()
//{
//    cout << "Hello World!" << endl;
//    Solution solution;
////    string s = "25525511135";
////    string s = "0000";
//    string s = "101023";
//    vector<string> ret = solution.restoreIpAddresses(s);
//    cout << "End" << ret.size() << endl;
//}
